#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [&](vector<int>& v1, vector<int>& v2) {
            return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
            });
        int n = envelopes.size();
        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        for (int i = 1; i < n; i++)
        {
            if (envelopes[i][1] > ret.back()) ret.push_back(envelopes[i][1]);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (ret[mid] < envelopes[i][1]) left = mid + 1;
                    else if (ret[mid] > envelopes[i][1]) right = mid;
                    else left = right = mid;
                }
                ret[left] = envelopes[i][1];
            }
        }
        return ret.size();
    }
};